package LeetCode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;

public class LC_381_InsertDeleteGetRandomO1Duplicatesallowed {

    public static void main(String[] args) {

    }

    public class RandomizedCollection {
        HashMap<Integer, HashSet<Integer>> map1;
        HashMap<Integer, Integer> map2;
        Random r;

        public RandomizedCollection() {
            map1 = new HashMap<>();
            map2 = new HashMap<>();
            r = new Random();
        }

        public boolean insert(int val) {
            int size2 = map2.size();
            map2.put(size2 + 1, val);
            if (map1.containsKey(val)) {
                map1.get(val).add(size2 + 1);
                return false;
            } else {
                HashSet<Integer> set = new HashSet<>();
                set.add(size2 + 1);
                map1.put(val, set);
                return true;
            }
        }

        public boolean remove(int val) {
            if (map1.containsKey(val)) {
                HashSet<Integer> set = map1.get(val);
                int toRemove = set.iterator().next();
                set.remove(toRemove);
                if (set.size() == 0) map1.remove(val);
                if (toRemove == map2.size()) {
                    map2.remove(toRemove);
                    return true;
                }
                int size2 = map2.size();
                int key = map2.get(size2);
                HashSet<Integer> setChange = map1.get(key);
                setChange.remove(size2);
                setChange.add(toRemove);
                map2.remove(size2);
                map2.remove(toRemove);
                map2.put(toRemove, key);
                return true;
            }
            return false;
        }

        public int getRandom() {
            if (map1.size() == 0) return -1;
            if (map2.size() == 1) return map2.get(1);
            return map2.get(r.nextInt(map2.size()) + 1);
        }

    }
}